#include <iostream>
#include <string>
#include <vector>
using namespace std;
typedef int* SStable; 
typedef string Stable;
typedef char keytype;
//静态表查找

int Search_Seq(Stable a,keytype key)
{
    for(int i=0;i<a.length();i++)
    {
        if(a[i]==key)
        return i;

    }
    return -1;
}

//有序表的折半查找
int Search_bin(SStable st,int x)
{
    int low=1;
    int high=sizeof(st)/sizeof(int )-1;
    while(low<=high)
    {
        int mid=(low+high)/2;
        if(x==*(st+mid))
        {
            return mid;
        }
        else if(x<*(st+mid))
        {
            high=mid-1;

        }
        else low=mid+1;

    }
    return -1;
}

//二叉排序树
typedef struct BiTNode{
    int data;
    struct BiTNode *lchild,*rchild;
    struct BiTNode *parent;

}BiTNode,*BiTree;

BiTree searchbst(BiTree T,int key,BiTNode *endleaf)
{
    if(!T) return NULL;
    if(T->data==key) {endleaf=T;return T;}
    else if(T->data<key) searchbst(T->lchild,key,T->lchild);
    else searchbst(T->rchild,key,T->rchild);
}

bool insertbst(BiTree T,int key)
{
    BiTNode* endleafa=new BiTNode;
    if(!searchbst(T,key,endleafa))
    {
        BiTNode s;
        s.data=key;
        s.lchild=NULL;
        s.rchild=NULL;
        if(endleafa->data==-1)
        {
            T=&s;
        }
        else if(key<endleafa->data) endleafa->lchild=&s;
        else endleafa->rchild=&s;
        return 1;
    }
    return 0;
}

bool deletebst(BiTree T,int key)
{
    BiTNode* endleafa=new BiTNode;
    if(!searchbst(T,key,endleafa))return 0;
    deletetree (endleafa);
}
void deletetree(BiTNode* aim)
{
    if(aim->lchild==NULL&&aim->rchild==NULL)//没有子树
    {
        delete aim;
        return;
    }
    if(aim->lchild==NULL&&aim->rchild!=NULL)
    {
        aim->parent->rchild=aim->rchild;
    }
    else if(aim->rchild==NULL&&aim->lchild!=NULL)
    {
        aim->parent->lchild=aim->lchild;
    }
    else//左右子树均存在
    {
        BiTNode* a=aim->lchild,*b=aim;
        while(a->rchild!=NULL) a=a->rchild;
        a->rchild=b;
        aim->parent->rchild=a;
        delete aim;
    }
} 